#include <stdio.h>
#include <math.h>

#include "myComplex.h"
#include "fft.h"

void fftShow(myComplex *val, int n)
{
    real a, p;

    for(int i = 0; i < n / 2; ++i)
    {
        a = myComplex_Modulus(&val[i]) / fft_N;
        a *= (0 == i ? 1 : 2);
        p = atan(val[i].Im / val[i].Re);
        printf("Point %d : f = %.3f Hz, A = %.3f, P = %.3f\n", i, (float)i * fft_Fs / fft_N, a, p);
    }
}

void fft(myComplex *val, int n, myComplex *buf)
{
    myComplex z, w, *vo, *ve;

    if(n > 1)
    {
        ve = buf;
        vo = buf + n / 2;
        /* 分离奇偶序列 */
        for(int k = 0; k < n / 2; ++k)
        {
            ve[k] = val[2 * k];
            vo[k] = val[2 * k + 1];
        }
        /* 分别对奇偶序列递归 */
        fft(ve, n / 2, val);
        fft(vo, n / 2, val);
        for(int k = 0; k < n / 2; ++k)
        {
            w = myComplex_Make(cos(2.0 * PI * k / (double)n), -sin(2.0 * PI * k / (double)n));
            myComplex_Mul(&z, &w, &vo[k]);
            myComplex_Add(&val[k        ], &ve[k], &z);
            myComplex_Sub(&val[k + n / 2], &ve[k], &z);
        }
    }
}
